package q62_uniquePaths;

public class Solution_3 {

    /**
     * 数学解法，值得学习思考，同时降低了时间和空间复杂度
     * 从左上角到右下角的过程中，我们需要移动 m+n-2 次，其中有 m-1 次向下移动，n-1 次向右移动。
     * 因此路径的总数，就等于从 m+n-2 次移动中选择 m-1 次向下移动的方案数，即组合数
     *   (m - 1)
     * C (m + n - 2)
     * 因此很简单的通过一次循环即得到答案
     */
    public int uniquePaths(int m, int n) {
        long ans = 1;

        // 组合数的求法
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;

    }
}
